package 算法.其他算法;

import java.util.ArrayList;

public class JZ74和为S的连续正数序列 {
    //枚举
    public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer> >();
        int sum1 = 0;
        //因为序列至少两个数，因此枚举最多到该数字的一半向下取整
        int up = (sum - 1) / 2;
        //枚举左区间
        for(int i = 1; i <= up; i++){
            //从左区间往后依次连续累加
            for(int j = i; ;j++){
                sum1+=j;
                //大于目标和则跳出该左区间
                if(sum1 > sum) {
                    sum1 = 0;
                    break;
                }else if(sum1==sum){
                    //等于则找到了
                    sum1 = 0;
                    ArrayList<Integer> temp = new ArrayList<Integer>();
                    //记录线序的数字
                    for(int k = i; k <= j; k++)
                        temp.add(k);
                    res.add(temp);
                    break;
                }
            }
        }
        return  res;
    }

    //滑动窗口
    public ArrayList<ArrayList<Integer>> FindContinuousSequence2(int sum) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if(sum<=2)
            return res;
        int left = 1;
        int right = 1;
        int sum1 = 1;
        while (left<=sum/2){
            if(sum1<sum){
                right++;
                sum1+=right;
            }else if(sum1>sum){
                sum1-=left;
                left++;
            }else{
                ArrayList<Integer> alist = new ArrayList<>();
                for(int i=left;i<=right;i++)
                    alist.add(i);
                res.add(alist);
                sum1-=left;
                left++;
                right++;
                sum1+=right;
            }
        }
        return  res;
    }
}
